#!/usr/bin python3
# -*- coding: utf-8 -*-

from abc import abstractmethod
from typing import List


class Sort(object):
    """基于比较的排序算法模板类"""

    @staticmethod
    @abstractmethod
    def sort(data: list):
        raise NotImplementedError('sort: not implemented')

    @staticmethod
    def less(v: int, w: int) -> bool:
        return v < w

    @staticmethod
    def exch(data: List, i: int, j: int):
        data[i], data[j] = data[j], data[i]

    @staticmethod
    def show(data: list):
        print(data)

    @staticmethod
    def is_sorted(data: List):
        for i in range(1, len(data) - 1):
            if Sort.less(data[i], data[i - 1]):
                return False
        return True


class ShellSort(Sort):
    """希尔排序算法: 插入排序的改进算法"""
    @staticmethod
    def sort(data: list):
        n = len(data)
        # 确定h的值, 至少为N/3
        h = 1
        while h < n // 3:
            h = 3 * h + 1  # 1, 4, 13, 40, 121, 364, 1093...
        while h >= 1:  # 当h减小为1, 1有序即整个数组有序
            # 变为h有序
            for i in range(h, n):
                j = i
                while j >= h and ShellSort.less(data[j], data[j - h]):
                    ShellSort.exch(data, j, j-h)
                    j -= h
            h = h // 3


class MergeSort(Sort):
    """归并排序"""
    @staticmethod
    def sort(data: list, flag=True):
        lo = 0
        hi = len(data) - 1
        sorter = MergeSort()
        if flag:
            sorter._sort1(data, lo, hi)
        else:
            sorter._sort2(data)

    def _sort1(self, data: list, lo: int, hi: int):
        """自顶向下的递归算法"""
        if lo >= hi:
            return
        mid = (lo + hi) // 2
        self._sort1(data, lo, mid)   # 归并左侧
        self._sort1(data, mid+1, hi)  # 归并右侧
        self.merge(data, lo, mid, hi)

    def _sort2(self, data: list):
        """自底向上的归并"""
        length = len(data)
        i = 1
        while i < length:
            lo = 0
            while lo < length - i:
                self.merge(data, lo, lo+i-1, min(lo + i * 2 - 1, length - 1))
                lo += 2 * i
            i = 2 * i
        pass

    def merge(self, data: list, lo: int, mid: int, hi: int):
        """原地归并: 将原来有序的两个有序的数组合并成一个新的有序数组"""
        i = lo
        j = mid + 1

        # 复制数组
        aux = data.copy()
        length = len(data)

        for k in range(lo, hi):
            if i > length or j > hi:
                raise IndexError("i, j: " + str([i, j]) + "\n" + "len: " + str(length))
            if i > mid:
                data[k] = aux[j]
                j += 1
            elif j > hi:
                data[k] = aux[i]
                i += 1
            elif MergeSort.less(aux[i], aux[j]):
                data[k] = aux[i]
                i += 1
            else:
                data[k] = aux[j]
                j += 1


if __name__ == '__main__':
    pass
